starry sky tree
(a) This designation was given by some of the participants in the Japan Information Olympiad, and derives from the fact that it was the data structure required for the "Starry Sky" problem in the spring training camp of the Japan Information Olympiad 2009.
(b) The Starry Sky tree has several implementations and is just a generic term for them.
not much need if you can use a delayed seg tree.
Not doing delayed propagation when the operation is commutative reduces the amount of implementation and lightens the weight by a constant factor.
The starry sky tree, where the interval calculation side is additive and the interval summing side is max, is a typical example.
---
This page is auto-translated from /nishio/starry sky tree. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.